/**
 * @author ChaP
 * @date 2019/07/12
 * @describe:
 */
package CodingTest.AC20190712;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * leetcode - 524
 * 给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

 示例 1:

 输入:
 s = "abpcplea", d = ["ale","apple","monkey","plea"]

 输出:
 "apple"
 示例 2:

 输入:
 s = "abpcplea", d = ["a","b","c"]

 输出:
 "a"
 说明:

 所有输入的字符串只包含小写字母。
 字典的大小不会超过 1000。
 所有输入的字符串长度不会超过 1000。


 */
public class findLongestWord {
    public String findLongestWord(String s,List<String> d){
        if(d.size() == 0 ||s.length() == 0) return "";
        String res = "";
        int max = 0;
        String[] ss  = new String[d.size()];
        for(int i = 0;i<d.size();i++){
            ss[i] = d.get(i);
        }
        Arrays.sort(ss);
        for(int i = 0;i<d.size();i++){
            String temp = ss[i];
            int index = 1;// list 的index
            for(int j = 0;j<s.length();j++){
                if(s.charAt(j) == temp.charAt(index-1) &&index < temp.length()){
                    index ++;
                }
                if(index == temp.length()){
                    if(max<index){
                        max = index;
                        res = temp;
                        break;
                    }
                    break;
            }

            }

        }return res;
    }
    public String findLongestWord2(String s,List<String> d){
        String result = "";
        int maxLength = 0;
        // 挨个判断d中的每个str是否包含在s中
        // 如果包含，则用result来记录最长以及字典顺序最小的字符串，用maxLength来记录当前最大长度
        for(String str:d){
            int p1 =0,p2 = 0,len=0;
            while(p1 <s.length() && p2<str.length()){
                while(p1 < s.length()&& s.charAt(p1)!= str.charAt(p2)){
                    p1++;
                }
                if(p1 >= s.length()){
                    break;
                }
                //完成s和str的一个字符的匹配
                len++;
                p2++;
                p1++;
            }
            //当p2 == str.length()时，说明str中每一个字母都包含在s里了，这个str是满足题目的条件。
            if(p2 == str.length()){
                //str和当前最长的字符串一样长时，则将字典顺序小的更新为result
                if(len == maxLength){
                    if(str.compareTo(result) < 0){
                        result = str;
                    }
                }
                //str比当前最长的字符串长时，将str更新为result，同时更新maxLength
                if(len > maxLength){
                    maxLength = len;
                    result = str;
                }
            }
        }
        return result;



    }

    public static void main(String[] args) {
        findLongestWord fl = new findLongestWord();
        String s = "bab";
        List<String> str = new LinkedList<>();
//        str.add("ale");
//        str.add("apple");
//        str.add("monkey");
//        str.add("plea");
        str.add("ba");
        str.add("ab");
        str.add("a");
        str.add("b");
        System.out.println(fl.findLongestWord(s,str));
    }
}
